package com.zhanghp.class035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构<br/>
 * 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
 *
 * @author zhanghp
 * @since 2024/4/16 10:08
 */
public class Code04_InsertDeleteRandomDuplicatesAllowed {
    public static void main(String[] args) {
        RandomizedCollection a = new RandomizedCollection();
        a.insert(1);
        a.insert(10);
        a.insert(10);
        a.insert(100);
        System.out.println(a.getRandom());
    }

    static class RandomizedCollection {

        /**
         * key:val<br/>
         * set:对应key的索引集合
         */
        public Map<Integer, HashSet<Integer>> map;

        public ArrayList<Integer> arr;

        public RandomizedCollection() {
            map = new HashMap<>();
            arr = new ArrayList<>();
        }

        public boolean insert(int val) {
            // 不存在：true
            // 存在：false
            boolean ans = true;
            if (map.containsKey(val)) {
                ans = !ans;
            }
            HashSet<Integer> set = map.getOrDefault(val, new HashSet<>());
            set.add(arr.size());
            arr.add(val);
            map.put(val, set);
            return ans;

        }

        /**
         * 原理很简单，只是注释多（防止我以后看又要消耗时间成本）
         *
         * @param val
         * @return
         */
        public boolean remove(int val) {
            boolean ans = false;
            if (!map.containsKey(val)) {
                return ans;
            }
            // 获取删除值对应的set索引列表
            HashSet<Integer> valSet = map.get(val);
            // 获取删除值一个索引
            Integer valAnyIndex = valSet.iterator().next();
            // arr的处理前的大小
            int oldSize = arr.size() - 1;
            // 获取arr尾部节点的值 （用于替换remove后的索引的值）
            Integer endValue = arr.get(oldSize);

            // 移除val的索引
            valSet.remove(valAnyIndex);
            // set remove 顺序不能反（考虑到：最后一个节点移除情况
            // 设值移除的索引，val
            arr.set(valAnyIndex, endValue);
            // 移除arr末端索引（因为已经被设置了，所以remove掉）
            arr.remove(oldSize);
            // 获取map的末端值的set索引集合（用来处理上述步骤，新设置的index，并移除尾部索引）
            HashSet<Integer> endValueSet = map.get(endValue);
            // 顺序不能反（考虑到：最后一个节点移除情况）
            endValueSet.add(valAnyIndex);
            endValueSet.remove(oldSize);

            // 处理最后节点值的set
            if (endValueSet.isEmpty()) {
                map.remove(endValue);
            }
            // 处理remove值的索引set
            if (valSet.isEmpty()) {
                map.remove(val);
            }
            return !ans;
        }

        public int getRandom() {
            return arr.get((int) (Math.random() * arr.size()));
        }
    }


    static class RandomizedCollectionZuo {

        public HashMap<Integer, HashSet<Integer>> map;

        public ArrayList<Integer> arr;

        public RandomizedCollectionZuo() {
            map = new HashMap<>();
            arr = new ArrayList<>();
        }

        public boolean insert(int val) {
            arr.add(val);
            HashSet<Integer> set = map.getOrDefault(val, new HashSet<Integer>());
            set.add(arr.size() - 1);
            map.put(val, set);
            return set.size() == 1;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            HashSet<Integer> valSet = map.get(val);
            int valAnyIndex = valSet.iterator().next();
            int endValue = arr.get(arr.size() - 1);
            if (val == endValue) {
                valSet.remove(arr.size() - 1);
            } else {
                HashSet<Integer> endValueSet = map.get(endValue);
                endValueSet.add(valAnyIndex);
                arr.set(valAnyIndex, endValue);
                endValueSet.remove(arr.size() - 1);
                valSet.remove(valAnyIndex);
            }
            arr.remove(arr.size() - 1);
            if (valSet.isEmpty()) {
                map.remove(val);
            }
            return true;
        }

        public int getRandom() {
            return arr.get((int) (Math.random() * arr.size()));
        }
    }
}
